#include <iostream>
#include <vector>
using namespace std;

int maxProfit(vector<int> &prices);

int main(int argc, char **argv){

    vector<int> test;
    test.push_back(3);
    test.push_back(2);
    test.push_back(6);
    test.push_back(5);
    test.push_back(0);
    test.push_back(3);
    cout<<maxProfit(test);

    return 0;
}

int maxProfit(vector<int> &prices) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    // find ascending intervals
    if(prices.size() < 2){
        return 0;
    }

    // pMaxProfit[] store the max profit if sell that time
    int *pMaxProfit = new int[prices.size()];
    pMaxProfit[0] = 0;
    int buyPrice = prices[0];
    for(int i=1; i<prices.size(); ++i){
        if(prices[i] < buyPrice){
            buyPrice = prices[i];
            pMaxProfit[i] = 0;
        }
        else{
            pMaxProfit[i] = prices[i] - buyPrice;
        }
    }

    int maxProfit = 0;
    int maxProfitAfter = 0;
    int sellPrice = prices[prices.size()-1];
    buyPrice = prices[prices.size()-1];
    for(int i=prices.size()-1; i>=0; --i){
        int afterProfit = sellPrice - buyPrice;
        if(afterProfit > maxProfitAfter){
            maxProfitAfter = afterProfit;
        }
        int profit = pMaxProfit[i] + maxProfitAfter;
        if(profit > maxProfit){
            maxProfit = profit;
        }
        if(prices[i] > sellPrice){
            sellPrice = prices[i];
            buyPrice = prices[i];
        }
        if(prices[i] < buyPrice){
            buyPrice = prices[i];
        }
    }

    return maxProfit;
}